//class Solution {
//public:
//    ListNode* addInList(ListNode* head1, ListNode* head2) {
//
//        ListNode* newhead = new ListNode(0), * prev = newhead;
//        int tmp = 0;
//        ListNode* cur1 = reverseNode(head1), * cur2 = reverseNode(head2);
//        while (cur1 || cur2 || tmp)
//        {
//            if (cur1)
//            {
//                tmp += cur1->val;
//                cur1 = cur1->next;
//            }
//
//            if (cur2)
//            {
//                tmp += cur2->val;
//                cur2 = cur2->next;
//            }
//
//            ListNode* node = new ListNode(tmp % 10);
//            node->next = prev->next;
//            prev->next = node;
//            tmp /= 10;
//        }
//        prev = newhead->next;
//
//        delete newhead;
//        return prev;
//    }
//    ListNode* reverseNode(ListNode* head)
//    {
//        if (head == nullptr || head->next == nullptr) return head;
//        ListNode* newhead = reverseNode(head->next);
//        head->next->next = head;
//        head->next = nullptr;
//        return newhead;
//    }
//};


//class Solution {
//public:
//
//    ListNode* sortInList(ListNode* head) {
//        typedef pair<int, ListNode*> PIL;
//        vector<PIL> nodes;
//        ListNode* cur = head;
//        while (cur)
//        {
//            nodes.push_back(make_pair(cur->val, cur));
//            cur = cur->next;
//        }
//
//        sort(nodes.begin(), nodes.end(), [](PIL& node1, PIL& node2) {
//            return node1.first < node2.first;
//            });
//
//        ListNode* newhead = new ListNode(0), * prev = newhead;
//        for (auto& node : nodes)
//        {
//            prev->next = node.second;
//            prev = prev->next;
//        }
//        prev->next = nullptr;
//        prev = newhead->next;
//        delete newhead;
//        return prev;
//    }
//};




